1. Field of the Invention
The present invention generally relates to data embedding in digital images and, more particularly, to a data embedding scheme having a pre-specified upper bound on the amount of change in the value of the property altered by the process of data embedding.
2. Background Description
Traditionally, error diffusion has been used where a region of an image is modified in order to embed some information in the image. Then a negative change is made in another region of the image before information is embedded in the image so that the original state of the image is more or less maintained even after the information is embedded. This approach gives acceptable results in most of the cases, but problems arise in the case where the initial value is an extreme value, such as a predefined minimum and maximum value. If the initial value was equal to the predefined minimum value and the objective is to reduce the error by reducing its value, then the predefined minimum value obviously cannot be reduced. The error does not get diffused and tends to accumulate. In the worst case scenario it may not be possible to diffuse the error at all, and the scheme fails completely. Another fact is that this scheme first introduces an error, and then tries to subsequently diffuse it.
U.S. Pat. No. 5,785,249 to Mintzer et al. discloses an error diffusion strategy that maintains the average brightness of the image. According to this strategy, the modified pixel error is diffused by adjusting successive adjacent source pixel values away from the identified source pixel with decreasing amounts of the modified pixel error, in such a way that the total amount of the adjustment in the adjacent pixel values is equivalent to the modified pixel error and wherein the modified pixel value has incorporated the stamping information. This strategy, however, will not accommodate the case where the initial value is an extreme value.
It is therefore an object of the present invention to provide a solution to the data embedding problem under the additional constraint of a pre-specified upper bound on the amount of change in the value of the property.
For compression tolerant data hiding in digital images, a property in which the required information can be embedded is required. The property should be such that the value obtained from the property before and after a lossy compression like JPEG (Joint Picture Expert Group) compression does not change by a significant amount, and the change should be bounded. The property should be such that the value by this property as obtained from the image will not vary due to JPEG compression, but only due to malicious tampering. Thus, the value obtained from the property needs to be stored so that a comparison may be carried out and the image verified.
Now the question is how to store the value obtained from the property in a secure manner. The information can be stored in the property itself. The image can be broken into subparts, and each part can be used to store some information. This information can be called the checksum, which uniquely represents that part of the image. The value range of the property is mapped to bits, and hence bits can be stored in subparts by slightly juggling its pixels to make the property lie in a certain range that represents the required bit. While juggling pixels in the subparts, care must be taken so that the value of the property for a larger image part or the complete image, which is being stored, itself does not change. This issue is called the error diffusion.
A new approach is presented to the data embedding problem. Instead of sequentially looking at regions for data embedding, the complete picture is considered in pre-deciding whether to increase or decrease the value in a particular region. Consideration is also given to the fact that blocks having predefined minimum and maximum values, respectively, are incapable of change in a particular direction. Another very important distinction is that previous schemes try to store some checksum information and try to manipulate the image so that it still results in the same checksum. In the present approach, an attempt is made to vary the checksum (stored information) and modify the image, so that the net resultant checksum corresponds to the modified image value.
The method of the claimed invention first involves determining if the embedding can be corrected and, if so, then embedding the data with a parameter, such as L, having a first value (|a1xe2x88x92b1|), where a1 is a number of microblocks with a property value equal to a pre-specified lower bound and an inherently embedded bit opposite of a bit to be embedded, and b1 is a number of microblocks with a property value equal to a pre-specified upper bound and an inherently embedded bit opposite of a bit to be embedded. If the embedding cannot be corrected, then an integral value, i, is calculated such that the new property value corresponding to this value belongs to the same property value interval, I1, and then embedding the data with a parameter, such as L, having the value (|a1xe2x88x92b1xe2x88x92i|). If no integral value exists that satisfies the above-mentioned criterion, then another integral value, k, is found that maps to a different property value interval. Then the data is embedded with a with a parameter L having a value (|a1xe2x88x92b1xe2x88x92k|). If a solution has not yet been found, then another integral value, xk, is found such that the amount by which the embedding error corresponding to the embedding of the property value corresponding to this integral value exceeds the error-correcting capability is minimized. Then embedding is done using the new integral value.